package leetcode.editor.cn;
//给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 3
//输出：5
// 
//
// 示例 2： 
//
// 
//输入：n = 1
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 19 
// 
// Related Topics 树 二叉搜索树 数学 动态规划 二叉树 
// 👍 2206 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution99 {
    // 备忘录，减少重复计数
    private int[][] memo;

    public int numTrees(int n) {
        // 备忘录的值初始化为 0
        memo = new int[n + 1][n + 1];
        return count(1, n);
    }

    /**
     * 计算闭区间 [lo, hi] 组成的 BST 个数
     * <p>
     * 假设{1,2,3,4,5}这些数字去构造 BST
     * 比如说我们固定3作为根节点，这个前提下能有几种不同的 BST 呢？
     * 根据 BST 的特性，根节点的左子树都比根节点的值小，右子树的值都比根节点的值大。
     * 所以如果固定3作为根节点，左子树节点就是{1,2}的组合，右子树就是{4,5}的组合。
     * 左子树的组合数和右子树的组合数乘积就是3作为根节点时的 BST 个数。
     *
     * @param lo
     * @param hi
     * @return
     */
    int count(int lo, int hi) {
        if (lo > hi) {
            return 1;
        }
        if (memo[lo][hi] > 0) {
            return memo[lo][hi];
        }
        int res = 0;
        for (int root = lo; root <= hi; root++) {
            int left = count(lo, root - 1);
            int right = count(root + 1, hi);
            res += left * right;
        }
        memo[lo][hi] = res;
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
